// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// using namespace std;
// int main()
//{
//     int n;
//     cin >> n;
//     vector<string>v;
//     for (int i = 1; i < n; i++)
//     {
//         string s;
//         cin >> s;
//         v.push_back(s);
//     }
//     sort(v.begin(), v.end());
//     string ans;
//     for (int i = n - 1; i >= 0; i--)
//         ans += v[i];
//     cout << ans;
//     return 0;
// }
// #include <functional>
// #include <iostream>
// using namespace std;
// using namespace placeholders;
//
// void func(int a, int b, int c,int d) {
//     cout << "a=" << a << ", b=" << b << ", c=" << c <<"d="<<d <<endl;
// }
// void func1(string s,int a) {
//     cout <<s<<a << endl;
// }
// int main() {
//     auto new_func = bind(func1, "aaa",_2); // �󶨲���
//     new_func(20); // �����º���
//     // ԭ�������ã�func(30, 10, 20)�������a=30, b=10, c=20
//     return 0;
// }
// #include<iostream>
// #include<queue>
// using namespace std;
// int arr[40][40];
// bool st[40][40];
// struct node {
//	int x, y;
// };
// int N;
// int xrr[4] = { 0,1,0,-1 };
// int yrr[4] = { 1,0,-1,0 };
// queue<node>q;
// bool bfs(int i, int j)
//{
//	int flag = 1;
//	node n{ i,j };
//	q.push(n);
//	st[i][j] = true;
//	while (q.size())
//	{
//		auto n1 = q.front();
//		q.pop();
//		int x = n1.x, y = n1.y;
//		if (x == 1 || x == N || y == 1 || y == N)flag = 0;;
//		//		cout<<x<<' '<<y<<' '<<st[x][y]<<endl;
//		for (int i = 0; i < 4; i++)
//		{
//			int x1 = x + xrr[i];
//			int y1 = y + yrr[i];
//			if (x1 >= 0 && y1 >= 0 && x1 <= N + 1 && y1 <= 1 + N && st[x1][y1] == 0 && arr[x1][y1] == 0) {
//				st[x1][y1] = 1;
//				q.push({ x1,y1 });
//			}
//		}
//	}
//	return flag;
// }
// int main()
//{
//	cin >> N;
//	for (int i = 1; i <= N; i++)
//	{
//		for (int j = 1; j <= N; j++)cin >> arr[i][j];
//	}
//	bfs(0, 0);
//	for (int i = 1; i <= N; i++)
//		for (int j = 1; j <= N; j++)
//		{
//			if (arr[i][j] == 0 && st[i][j] == 0)
//				arr[i][j] = 2;
//		}
//	for (int i = 1; i <= N; i++)
//	{
//		for (int j = 1; j <= N; j++)cout << arr[i][j] << ' ';
//		cout << endl;
//	}
//	return 0;
// }
// #include <functional>
// #include<iostream>
// void f(int* a) {
//     std::cout << *a;
// }
// int main() {
//     int* a = new int(3);
//
//     auto b = std::bind(f, a);
//     b();
//     delete a;
//
//     b();
//     return 0;
// }
// #include <functional>
// #include<iostream>
// void f(int a) {
//     std::cout << a;
// }
// int main() {
//     int a = 3;
//
//     auto b = std::bind(f, a);
//     b();
//     a = 4;
//
//     b();
//     return 0;
// }
// #include<iostream>
// #include<functional>
// class A {
// public:
//	int a = 10;
// };
// class B {
// public:
//	A* _a;
//	B(A* a) :_a(a){}
//	~B() {
//		delete _a;
//		std::cout << "---" << "\n";
//	}
//	B operator=(const B b) = delete;
//	B(const B& b) = delete;
//	A operator*() { return *_a; }
//	A* operator->() { return _a; }
// };
// int main()
//{
//
//	A *a=new A;
//	B b(a);
//	std::cout<<b->a;
// }
// #include <iostream>
// #include <string>
//
// int main() {
//     std::string str = "Hello, World! 123";
//     std::string upper_str = to_upper(str);
//     std::cout << "ԭ�ַ���: " << str << std::endl;
//     std::cout << "��д��: " << upper_str << std::endl;  // ���: HELLO, WORLD! 123
// }

// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// typedef long long LL;
// using namespace std;
// int main() {
//	LL n;
//	while (n--) {
//		LL sum;
//		int x;
//		cin >> sum;
//		cout << "digit" << endl;
//		cin >>x;
//		cout << "digit" << endl;
//		cin >> x;
//		cout << "mul 125000000000000000" << endl;
//		cin >> x;
//		if (x)//С����8
//		{
//			cout << "mul 250000000000000000" << endl;
//			cin >> x;
//			if (x) {//С�ڵ���4
//				cout << "mul 500000000000000000" << endl;
//				cin >> x;
//				if (x) {
//					// xiaoyu����2
//					{
//						cout << "mul 1000000000000000000" << endl;
//						cin >> x;
//						if (x)//��1{
//						{
//							LL k = sum - 1;
//							cout << "add " << k << endl;
//						}
//						else {//��2
//							LL k = sum - 2;
//							cout << "add " << k << endl;
//						}
//					}
//				}
//				else {//3,4
//					cout << "mul 333333333333333332" << endl;
//					cin >> x;
//					if (x)//��3{
//					{
//						LL k = sum - 3;
//						cout << "add " << k << endl;
//					}
//					else {//��2
//						LL k = sum - 4;
//						cout << "add " << k << endl;
//					}
//				}
//			}
//		}
//		fflush(stdout);
//	}
// }
// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// typedef long long LL;
// using namespace std;
// int main() {
//	LL n;
//	cin >> n;
//	while (n--) {
//		LL sum;
//		int x;
//		cin >> sum;
//		cout << "digit" << endl;
//		cin >> x;
//		cout << "digit" << endl;
//		cin >> x;
//		int l = 1, r = 16;
//		int num = 4;
//		LL ans = 0;
//		while (num--) {
//			int mid = (l + r) >> 1;
//			LL k = 1000000000;
//			k *= k;
//			k /= mid;
//			cout << "mul " <<k<< endl;
//			cin >> x;
//			if (num == 0)
//				ans = mid * k;
//			if (x) {
//				r = l + r >> 1;
//			}
//			else {
//				l = (l + r >> 1)+1;
//			}
//		}
//		LL k = sum - ans;
//		cout << "add " << k << endl;
//		cin >> x;
//		cout << "!" << endl;
//		fflush(stdout);
//	}
// }
// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// typedef long long LL;
// using namespace std;
// int main() {
//	LL n;
//	cin >> n;
//	while (n--) {
//		LL sum;
//		int x;
//		cin >> sum;
//		cout << "digit" << endl;
//		cin >> x;
//		cout << "digit" << endl;
//		cin >> x;
//		cout << "add " <<-8 << endl;
//		cin >> x;
//		cout << "add " << -4 << endl;
//		cin >> x;
//		cout << "add " << -2 << endl;
//		cin >> x;
//		cout << "add " << -1 << endl;
//		cin >> x;
//		cout << "add " << sum-1 << endl;
//		cin >> x;
//		cout << "!" << endl;
//		cin >> x;
//		fflush(stdout);
//		cout.flush();
//	}
// }
// #include<iostream>
// #include<string>
// #include<vector>
// #include<algorithm>
// typedef long long LL;
// using namespace std;
// int main() {
//     LL a;
//     cin >> a;
//     while (a--) {
//         LL x, y;
//         cin >> x >> y;
//         int arr[40] = { 0 };
//         int num = 0;
//         for (int i = 0; i < 35; i++) {
//             if ((y >> i) & 1) {
//                 arr[i] = true;
//                 num++;
//             }
//         }
//         if (y == 0) {
//             if (x == 1)
//                 cout << -1 << endl;
//             else if (x % 2) {
//                 cout << x + 3 << endl;
//             }
//             else cout << x << endl;
//             continue;
//         }
//         if (num >= x) {
//             cout << y << endl;
//         }
//         else {
//             if ((x-num) % 2==0)
//                 cout << y +  x-num << endl;
//             else {
//                 int j = 0;
//                 while (arr[j])j++;
//                 LL sum = pow(2, j);
//                 sum = (x-num - 1)+2 * sum + y;
//                 cout << sum << endl;
//             }
//         }
//     }
// }
// #include<iostream>
// #include<string>
// #include<vector>
// #include<math.h>
// #include<algorithm>
// typedef long long LL;
// using namespace std;
// int main() {
//     LL a;
//     cin >> a;
//     while (a--) {
//         LL x, y;
//         cin >> x >> y;
//         LL arr[40] = { 0 };
//         LL num = 0;
//         for (LL i = 0; i < 35; i++) {
//             if ((y >> i) & 1) {
//                 arr[i] = true;
//                 num++;
//             }
//         }
//         if (y == 0) {
//             if (x == 1)
//                 cout << -1 << endl;
//             else if (x % 2) {
//                 cout << x + 3 << endl;
//             }
//             else cout << x << endl;
//             continue;
//         }
//         if (num >= x) {
//             cout << y << endl;
//         }
//         else {
//             if ((x - num) % 2 == 0)
//                 cout << y + x - num << endl;
//             else {
//                 if (num > 1) {
//                     LL sum = (x - num + 1) + y;
//                     cout << sum << endl;
//                 }
//                 else {
//                     LL j = 0;
//                     LL k = 1;
//                     while (arr[j])j++, k *= 2;;
//                     cout << x -2+y+k*2 << endl;
//                 }
//             }
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main() {
//     int n;
//     cin >> n;
//     while (n--) {
//         int sum = 0;
//         cin >> sum;
//         int last = -10;
//         int ans = 0;
//         int flag = 0;
//         for (int i = 0; i < sum; i++) {
//             int x;
//             cin >> x;
//             if (flag == 0 && x >= last);//����;
//             else if (flag == 0 && x < last)flag = 1;
//             else if (flag == 1 && x <= last);
//             else if (flag == 1 && x > last)ans++, flag = 0;
//             last = x;
//         }
//         ans++;
//         cout << ans << endl;
//     }
// }
// #include<bits/stdc++.h>
// typedef long long LL;
// using namespace std;
// struct D {
//     LL a, b;
//     bool operator<(const struct D d) {
//         return a + b < d.a + d.b;
//     }
// }arr[1010];
// int main()
//{
//     LL num, sum;
//     cin >> num >> sum;
//     for (int i = 1; i <= num; i++) {
//         cin >> arr[i].a >> arr[i].b;
//     }
//     sort(arr + 1, arr + num + 1);
//     LL ans1 = 1, ans2 = 0;
//     while (ans1<=num&&ans2 <= sum) {
//         ans2 += arr[ans1].a + arr[ans1].b;
//         ans1++;
//     }
//     ans1--;
//     LL ret = ans1-1;
//     if (ans2 + arr[ans1].a / 2 + arr[ans1].b <= sum)ret =max(ret, ans1);
//     sum -= (arr[ans1-1].a + arr[ans1-1].b);
//     sum += (arr[ans1 - 1].a / 2 + arr[ans1 - 1].b);
//     if (ans2 + arr[ans1].a+ arr[ans1].b <= sum)ret = max(ret, ans1);
//     cout << ans1 << endl;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const LL N = 2e5 + 10;
// LL arr[N];
// int main() {
//     LL t;
//     cin >> t;
//     while (t--) {
//         LL n, k;
//         cin >> n >> k;
//         LL sum = 0;
//         LL Max = 0, Min = 0x3f3f3f3f3f;
//         int Num_Max = 0;
//         for (int i = 1; i <= n; i++)
//         {
//             cin >> arr[i];
//             Min = min(Min, arr[i]);
//             sum += arr[i];
//             if (Max < arr[i]) {
//                 Num_Max=1;
//                 Max = arr[i];
//             }
//             else if (Max == arr[i]) {
//                 Num_Max++;
//             }
//         }
//         if (Max - Min-1 > k) {
//             cout << "Jerry" << endl;
//         }
//         else if(Max-Min-1==k&&Num_Max>1)
//             cout << "Jerry" << endl;
//
//         else if (sum % 2) {
//             cout << "Tom" << endl;
//         }
//         else {
//             cout << "Jerry" << endl;
//         }
//
//     }
//
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const LL N = 2e5 + 10;
// LL arr[N];
// int main() {
//     LL t;
//     cin >> t;
//     while (t--) {
//         LL n, k;
//         cin >> n >> k;
//         string s;
//         cin >> s;
//         s = " " + s;
//         for (LL i = 1; i <= n; i++)
//             cin >> arr[i];
//         LL Max = -0x3f3f3f3f3f3f;
//         LL x = 0, last = 0;
//         for (LL i = 1; i <= n; i++) {
//             if (s[i] == '1')
//             {
//                 x =max(x+ arr[i],arr[i]);
//                 Max = max(Max, x);
//             }
//             else {
//                 if (last + 1 == i) {
//                     last++;
//                 }
//                 else {
//                     Max = max(Max, x);
//                     x = 0;
//                     last = i;
//                 }
//             }
//         }
//         Max = max(Max, x);
//         if (Max > k) cout << "No" << endl;
//         else {
//             LL flag = 0;
//             for (LL i = 1; i <= n; i++)
//                 if (s[i] == '0')flag = 1;
//             if (flag == 0 && Max != k) {
//                 cout << "No" << endl;
//             }
//             else if (Max == k) {
//                 cout << "Yes" << endl;
//                 for (LL i = 1; i <= n; i++) {
//                     if (s[i] == '1')
//                         cout << arr[i] << ' ';
//                     else
//                         cout << (LL)-1e17 << endl;
//                 }
//                 cout << endl;
//             }
//             else {
//                 cout << "Yes" << endl;
//                 LL i = 1;
//                 while (s[i] == '1')i++;
//                 LL pos = i - 1;
//                 LL sum = 0;
//                 LL Max1 = 0;
//                 while (pos > 0) {
//                     sum += arr[pos];
//                     pos--;
//                     Max1 = max(Max1, sum);
//                 }
//                 pos = i + 1;
//                 sum = 0;
//                 LL Max2 = 0;
//                 while (pos <= n && s[pos] == '1') {
//                     sum += arr[pos];
//                     pos++;
//                     Max2 = max(Max2, sum);
//                 }
//                 LL ans = k - Max1 - Max2;
//                 arr[i] = ans;
//                 s[i] = '1';
//                 for (LL i = 1; i <= n; i++) {
//                     if (s[i] == '1')
//                         cout << arr[i] << ' ';
//                     else
//                         cout << (LL)-1e17 << ' ';
//                 }
//                 cout << endl;
//             }
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// int main() {
//	int arr[10] = { -10,-20,-30 };
//	int Max = -100;
//	int sum = 0;
//	for (int i = 0; i < 3; i++) {
//		sum = max(sum + arr[i], arr[i]);
//		Max = max(Max, sum);
//	}
//	cout << Max;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL arr[100000];
// priority_queue<LL, vector<LL>, greater<LL>>pq;
// int main() {
//     LL a, n;
//     cin >> a >> n;
//     for (int i = 1; i <= a; i++)cin >> arr[i];
//     for (int i = 1; i <= n; i++)
//         pq.push(arr[i]);
//     LL sum = 0;
//     int pos = n;
//     while (pq.size()) {
//         vector<int>v;
//         int x = pq.top();
//         while (pq.size()) {
//             v.push_back(pq.top());
//             pq.pop();
//         }
//         for (auto& i : v) {
//             i -= x;
//             if (i)
//                 pq.push(i);
//         }
//         sum += x;
//
//         while (pos < a && pq.size() < n) {
//             pos++;
//             pq.push(arr[pos]);
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// const int N = 5e5 + 10;
// typedef long long LL;
// LL arr[N];
// LL brr[N];
// LL sum;
// void guibing(LL arr[], LL l, LL r) {
//     if (l >= r)return;
//     LL l1 = l, r1 = l + r >> 1;
//     LL l2 = (l + r >> 1) + 1, r2 = r;
//     guibing(arr, l1, r1);
//     guibing(arr, l2, r2);
//     LL j = l2;
//     int pos = 1;
//     while ((l1 <= r1) && (l2 <= r2)) {
//         if (arr[l1] <= arr[l2])
//             brr[pos++] = arr[l1++];
//         else
//         {
//             brr[pos++] = arr[l2++];
//             sum += (r1 - l1 + 1);
//         }
//     }
//     while (l1 <= r1)
//         brr[pos++] = arr[l1++];
//     while (l2 <= r2)
//         brr[pos++] = arr[l2++];
//     j = 1;
//     for (LL i = l; i <= r; i++)arr[i] = brr[j++];
// }
// int main() {
//     LL n;
//     cin >> n;
//     for (LL i = 1; i <= n; i++)
//         cin >> arr[i];
//     guibing(arr, 1, n);
//     cout << sum << endl;
// }
// #include<bits/stdc++.h>
// typedef long long LL;
// using namespace std;
// const int N = 1e5 + 10;
// int n, m, w;
// int e[N], ne[N], h[N], jiaqian[N], jiazhi[N];
// int idx;
// void add(int a, int b) {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
// }
// bool is[N];
// vector<int>vv1;
// vector<int>vv2;
// void f(int root) {
//     int sum1 = 0, sum2 = 0;
//     queue<int>q;
//     q.push(root);
//     is[root] = true;
//     while (q.size()) {
//         int r = q.front();
//         sum1 += jiaqian[r];
//         sum2 += jiazhi[r];
//         q.pop();
//         for (int i = h[r]; i != -1; i = ne[i]) {
//             if (is[e[i]] == false) {
//                 q.push(e[i]);
//                 is[e[i]] = true;
//             }
//         }
//     }
//     vv1.push_back(sum1);
//     vv2.push_back(sum2);
// }
// int dp[10010];
// int main() {
//     vv1.push_back(0);
//     vv2.push_back(0);
//     memset(h, -1, sizeof h);
//     cin >> n >> m >> w;
//     for (int i = 1; i <= n; i++)cin >> jiaqian[i] >> jiazhi[i];
//     for (int i = 1; i <= m; i++) {
//         int x, y;
//         cin >> x >> y;
//         add(x, y);
//         add(y, x);
//     }
//     for(int i=1;i<=n;i++)if(is[i]==0)
//     f(i);
//     for (int i = 1; i < vv1.size(); i++)
//         for (int v = w; v >= vv1[i]; v--)
//         {
//             dp[v] = max(dp[v], dp[v - vv1[i]] + vv2[i]);
//         }
//     cout << dp[w]<<endl;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const int N = 1e6 + 10;
// LL arr[N];
// LL chafen[N];
// struct date {
//     LL a, b, c;
// }brr[N];
// LL NN, m;
// bool check(int n) {
//     for (int i = 1; i <= NN; i++)chafen[i] = arr[i] - arr[i - 1];
//     for (int i = 1; i <= n; i++)
//     {
//         int a = brr[i].a;
//         int b = brr[i].b;
//         int c = brr[i].c;
//         chafen[b] -= a;
//         chafen[c + 1] += a;
//     }
//     for (int i = 1; i <= NN; i++)
//     {
//         chafen[i] += chafen[i - 1];
//         if (chafen[i] < 0)
//             return 0;
//     }
//     return true;
// }
// int main() {
//     cin >> NN >> m;
//     for (int i = 1; i <= NN; i++)cin >> arr[i];
//     for (int i = 1; i <= m; i++) {
//         cin >> brr[i].a >> brr[i].b >> brr[i].c;
//     }
//     int l = 1, r = m;
//     while (l < r) {
//         int mid = l + r >> 1;
//         if (check(mid) == 0)r = mid;
//         else l = mid + 1;
//     }
//     if (check(l))
//         cout << 0;
//     else {
//         cout << -1 << endl << l;
//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef unsigned long long LL;
// LL arr[5010][5010];
// LL vis[5010][5010];
// int main() {
//     ios::sync_with_stdio(false);
//     cin.tie(0);
//     cout.tie(0);
//     LL n, m, k;
//     cin >> n >> m >> k;
//     for (int j = 1; j <= m; j++)
//     {
//         int x, y, z;
//         cin >> x >> y >> z;
//         vis[x][y] += z;
//         vis[x + k][y] -= z;
//         vis[x][y + k] -= z;
//         vis[x + k][y + k] += z;
//     }
//     long long ans = 0;
//     for (int i = 1; i + k - 1 <= n; i++)
//         for (int j = 1; j + k - 1 <= m; j++)
//         {
//             long long x = vis[i][j];
//             if (x > 0)
//                 ans += x;
//             else ans -= x;
//             vis[i][j] -= x;
//             vis[i + k][j] += x;
//             vis[i][j + k] += x;
//             vis[i + k][j + k] -= x;
//         }
//     for (int i = 1; i <= n; i++)
//         for (int j = 1; j <= m; j++) {
//             if (vis[i][j]) {
//                 cout << -1;
//                 return 0;
//             }
//         }
//     cout << ans;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// const int N = 2e5 + 10;
// LL arr[N];
// int main() {
//     int t;
//     cin >> t;
//     while (t--) {
//         int n, m, p, q;
//         cin >> n >> m >> p >> q;
//         if (n / p * q > m)cout << "NO" << endl;
//         else {
//             // for(int i=1;i<=n;i++)
//             // {
//             //     if(i%p==1)arr[i]=q;
//             //     else arr[i]=0;;
//             // }
//             // arr[n]=q;
//             cout << "YES" << endl;
//         }
//     }
//
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int arr[600][600];
// int main() {
//     int t;
//     cin >> t;
//     while (t--) {
//         int n;
//         cin >> n;
//         int nn = n;
//         if (n % 2 == 0)n++;
//         int k = 0;
//         int center = (n + 1) / 2;
//         k = 0;
//         arr[center][center] = k++;
//         for (int i = 1; i <= n / 2; i++)
//         {
//             for (int j = center-i+1; j <= center+i; j++) {
//                 arr[center + i][j] = k++;
//             }
//             for (int j = i + center - 1; j >= center-i+1; j--)
//                 arr[j][center + i] = k++;
//             for (int j = center + i; j >= center - i; j--)
//                 arr[center - i][j] = k++;
//             for (int j = center - i + 1; j <= i + center; j++)
//                 arr[j][center - i] = k++;
//         }
//         int flag = 0;
//         if (nn % 2 == 0)flag = 1;
//         for (int i = 1+flag; i <= n; i++)
//         {
//             for (int j = 1+flag; j <= n; j++)
//                 cout << arr[i][j] << ' ';
//             cout << endl;
//         }
//
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int tr11[200010];
// int tr2[200010];
// int ji[200010];
// int ou[200010];
// int n;
// int lowbit(int x) {
//     return x & (-x);
// }
// void update1(int pos) {
//     while (pos <= n) {
//         tr11[pos]++;
//         pos += lowbit(pos);
//     }
// }
// LL query1(int pos) {
//     LL sum = 0;
//     while (pos) {
//         sum += tr11[pos];
//         pos -= lowbit(pos);
//
//     }
//     return sum;
// }
// void update2(int pos) {
//     while (pos <= n) {
//         tr2[pos]++;
//         pos += lowbit(pos);
//     }
// }
// LL query2(int pos) {
//     LL sum = 0;
//     while (pos) {
//         sum += tr2[pos];
//         pos -= lowbit(pos);
//
//     }
//     return sum;
// }
// int main() {
//     int t;
//     cin >> t;
//     while (t--) {
//         memset(tr2, 0, sizeof tr2);
//         memset(tr11, 0, sizeof tr11);
//
//         vector<int>v;
//         cin >> n;
//         int num1 = 1, num2 = 1;
//         for (int i = 1; i <= n; i++)
//             if (i % 2)cin >> ji[num1++]; else cin >> ou[num2++];
//             int ni1 = 0, ni2 = 0;
//             num1--, num2--;
//             for (int i = num1; i; i--) {
//                 ni1 += query1(ji[i] - 1);
//                 update1(ji[i]);
//             }
//             for (int i = num2; i; i--) {
//                 ni2 += query2(ou[i] - 1);
//                 update2(ou[i]);
//             }
//             bool is = (ni1%2) ^ (ni2%2);
//             cout << ni1 <<' '<< ni2 << endl;
//             sort(ji+1, ji + num1+1);
//             sort(ou+1, ou + num2+1);
//  /*           for (int i = 1; i <= num1; i++)cout << ji[i] << ' ';
//             for (int i = 1; i <= num2; i++)cout << ou[i] << ' ';
//             cout << "--" << endl;*/
//             for (int i = 1, j = 1, k = 1; i <= n; i++)
//                 if (i % 2)v.push_back(ji[j++]);
//                 else v.push_back(ou[k++]);
//             if (is)swap(v[n - 1], v[n - 3]);
//             for (auto i : v)
//                 cout << i << ' ';
//             cout << endl;
//         }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// unordered_map<LL, int>mp;
// LL n;
// LL arr[40];
//
// void dfs1(LL pos, LL sum) {
//     if (sum > (n + 1) * n / 2 / 2)return;
//     if (pos == n / 2) {
//         mp[sum]++;
//         return;
//     }
//     dfs1(pos + 1, sum + pos);
//     dfs1(pos + 1, sum);
// }
// LL dfs2(int pos, LL sum) {
//     if (sum > (n + 1) * n / 2 / 2)return 0;
//     if (pos == n + 1) {
//         return mp[n * (n + 1) / 2 / 2 - sum];
//     }
//     LL ans = dfs2(pos + 1, sum + pos);
//     ans += dfs2(pos + 1, sum);
//     return ans;
// }
// int main() {
//     cin >> n;
//     if (n * (n + 1) / 2 % 2)cout << 0;
//     else {
//         dfs1(1, 0);
//         cout << dfs2(n / 2, 0) / 2 << endl;
//     }
//
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// bool is[10][10];
// int num;
// int dx[4] = { 1,0,-1,0 };
// int dy[] = { 0,-1,0,1 };
// LL n, m;
//
// void dfs(int x, int y) {
//     if (x == 0 || x == n || y == 0 || y == m) { num++; return; }
//     for (int i = 0; i < 4; i++)
//     {
//         int x1 = x + dx[i];
//         int y1 = y + dy[i];
//         if (is[x1][y1])continue;
//         is[x1][y1] = true;
//         dfs(x1, y1);
//         is[x1][y1] = false;
//     }
// }
// int main() {
//     cin >> n >> m;
//     for (int i = 1; i < n; i++)
//     {
//         is[i][0] = true;
//         is[i][1] = true;
//         dfs(i, 1);
//         is[i][0] = true;
//         is[i][1] = true;
//     }
//     for (int i = 1; i < m; i++)
//     {
//         is[0][i] = true;
//         is[1][i] = true;
//         dfs(1, i);
//         is[0][i] = true;
//         is[1][i] = true;
//     }
//     cout << sum;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main() {
//     while (1) {
//         LL a, b, c;
//         cin >> a >> b >> c;
//         int flag1 = 0, flag2 = 0, flag3 = 0;
//         if (a == 0)flag1 = 1;
//         if (b == 0)flag2 = 1;
//         if (c == 0)flag3 = 1;
//
//         LL x = (a - 1) / 3 + (b - 1) / 3 + (c - 1) / 3;
//         a = a % 3;
//         b = b % 3;
//         c = c % 3;
//         if (a == 0 && flag1 == 0)a = 3;
//         if (b == 0 && flag2 == 0)b = 3;
//         if (c == 0 && flag3 == 0)c = 3;
//         int arr[3];
//         arr[0] = a;
//         arr[1] = b;
//         arr[2] = c;
//         sort(arr, arr + 3);
//         if (arr[0] == arr[2])
//             x += arr[0];
//         else if (arr[0] == 2)x += 2;
//         else if (arr[0] == 1 && arr[1] == 3)x += 2;
//         else if (arr[0] == 1)x += 1;
//         else x += (b / 3) + c / 3;
//         cout << x << endl;
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main() {
//     LL a, b, c;
//     cin >> a >> b >> c;
//     LL ans = b * pow(3, a + 2);
//     ans += 99;
//     ans /= 100;
//     ans *= 100;
//     ans *= (3 + !c);
//     cout << ans;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int num[100010];
// LL n, m;
// map<LL, vector<LL>>mp;
// LL chudu[100010];
// LL rudu[100010];
// LL idx;
// LL e[100010], ne[100010], h[100010];
// void add(LL a, LL b) {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//    // chudu[a]++;
//     rudu[b]++;
// }
// int dfs(int n_, int m_) {
//     int x = 0;
//     for (int i = 0; i < mp[n_].size(); i++)
//     {
//         if (m_ + num[mp[n_][i]] > m)
//             m_ += num[mp[n_][i]];
//         else { return dfs(mp[n_][i], m_); };
//     }
//     return n_;
//
// }
// void dfs(int root) {
//     for (int i = h[root]; i != -1; i = ne[i]) {
//         int j = e[i];
//         dfs(j);
//         num[root] += num[j];
//     }
//     num[root]++;
// }
// int main() {
//     cin >> n;
//     memset(h, -1, sizeof h);
//     for (int i = 1; i <= n; i++) {
//         int x;
//         cin >> x;
//         while (x--) {
//             int y;
//             cin >> y;
//             //num[i] += num[y];
//             mp[i].push_back(y);
//             add(i, y);
//         }
//         num[i]++;
//     }
//     queue<int>q;
//    // for (int i = 1; i <= n; i++)if (chudu[i] == 0)num[i]=1;
//     for (int i = 1; i <= n; i++)if (rudu[i] == 0)dfs(i);
//     LL m;
//     cin >> m;
//     for (int i = 1; i <= n; i++)cout << num[i] << ' ';
//     cout << endl;
//     for (int i = 0; i < mp[n].size(); i++) {
//         if (m > num[mp[n][i]])m -= num[mp[n][i]];
//         else {
//             cout << dfs(mp[n][i], 0);
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int num[100010];
// LL n, m;
// map<LL, vector<LL>>mp;
// LL rudu[100010];
// LL idx;
// LL e[100010], ne[100010], h[100010];
// void add(LL a, LL b) {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//     rudu[b]++;
// }
// int dfs(int n_, int m_) {
//     int x = 0;
//     for (int i = 0; i < mp[n_].size(); i++)
//     {
//         if (m_ + num[mp[n_][i]] > m)
//             m_ += num[mp[n_][i]];
//         else { return dfs(mp[n_][i], m_); };
//     }
//     return n_;
//
// }
// void dfs(int root) {
//     for (int i = h[root]; i != -1; i = ne[i]) {
//         int j = e[i];
//         dfs(j);
//         num[root] += num[j];
//     }
//     num[root]++;
// }
// int main() {
//     cin >> n;
//     memset(h, -1, sizeof h);
//     for (int i = 1; i <= n; i++) {
//         int x;
//         cin >> x;
//         while (x--) {
//             int y;
//             cin >> y;
//             mp[i].push_back(y);
//             add(i, y);
//         }
//         num[i]++;
//     }
//     queue<int>q;
//     for (int i = 1; i <= n; i++)if (rudu[i] == 0)dfs(i);
//     LL m;
//     cin >> m;
//     for (int i = 0; i < mp[n].size(); i++) {
//         if (m > num[mp[n][i]])m -= num[mp[n][i]];
//         else {
//             cout << dfs(mp[n][i], 0);
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int num[100010];
// LL n, m;
// map<LL, vector<LL>>mp;
// LL rudu[100010];
// LL idx;
// LL e[100010], ne[100010], h[100010];
// void add(LL a, LL b) {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//     rudu[b]++;
// }
// int dfs(int n_, int m_) {
//     int x = 0;
//     for (int i = 0; i < mp[n_].size(); i++)
//     {
//         if (m_ + num[mp[n_][i]] < m)
//             m_ += num[mp[n_][i]];
//         else { cout << m_ +num[mp[n_][i]]<< ' '<<m<< endl; return dfs(mp[n_][i], m_); };
//     }
//     return n_;
//
// }
// void dfs(int root) {
//     if (num[root])return ;
//     for (int i = h[root]; i != -1; i = ne[i]) {
//         int j = e[i];
//         dfs(j);
//         num[root] += num[j];
//     }
//     num[root]++;
// }
// int main() {
//     cin >> n;
//     memset(h, -1, sizeof h);
//     for (int i = 1; i <= n; i++) {
//         int x;
//         cin >> x;
//         while (x--) {
//             int y;
//             cin >> y;
//             mp[i].push_back(y);
//             add(i, y);
//         }
//     }
//
//     queue<int>q;
//     for (int i = 1; i <= n; i++)if (rudu[i] == 0)dfs(i);
//     for (int i = 1; i <= n; i++)cout << num[i] << ' ';
//
//     cout << endl;
//     cin >> m;
//             cout << dfs(n, 0);
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL num[100010];
// LL n, m;
// vector<vector<LL>>mp(100010);
// LL rudu[100010];
// LL idx;
// LL e[100010], ne[100010], h[100010];
// void add(LL a, LL b) {
//     e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//     rudu[b]++;
// }
// LL dfs(LL n_, LL m_) {
//     LL x = 0;
//     for (LL i = 0; i < mp[n_].size(); i++)
//     {
//         if (m_ + num[mp[n_][i]] < m)
//             m_ += num[mp[n_][i]];
//         else { return dfs(mp[n_][i], m_); }
//     }
//     return n_;
//
// }
// void dfs(LL root) {
//     if (num[root])return;
//     for (LL i = h[root]; i != -1; i = ne[i]) {
//         LL j = e[i];
//         dfs(j);
//         num[root] += num[j];
//     }
//     num[root]++;
// }
// int main() {
//     cin >> n;
//     memset(h, -1, sizeof h);
//     for (int i = 1; i <= n; i++) {
//         LL x;
//         cin >> x;
//         while (x--) {
//             LL y;
//             cin >> y;
//             mp[i].push_back(y);
//             add(i, y);
//         }
//     }
//     for (int i = 1; i <= n; i++)if (rudu[i] == 0)dfs(i);
//     cin >> m;
//     cout << dfs(n, 0);
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main() {
//     string s;
//     cin >> s;
//     LL sum = 0;
//     string ss;
//     for (int i = 0; i < s.size(); i++)
//         if (i == 1 || i == 5 || i == 11)
//             ss += s[i];
//     for (int i = 0; i < ss.size(); i++)
//         sum = sum + (i + 1) * (s[i] - '0');
//     sum %= 11;
//     char ans = sum;
//     if (ans == 10)ans = 'X';
//     if (s[s.size() - 1] == ans)cout << "Right";
//     else {
//         s[s.size() - 1] = ans;
//         cout << ans;
//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main() {
//     string s;
//     cin >> s;
//     LL sum = 0;
//     string ss;
//     for (int i = 0; i < s.size(); i++)
//         if (i != 1 && i != 5 && i != 11 && i != 12)
//             cout << s[i]
//             for (int i = 0; i < ss.size(); i++)
//                 sum = sum + (i + 1) * (ss[i] - '0');
//     cout << sum << endl;
//     sum %= 11;
//     char ans = sum;
//     if (ans == 10)ans = 'X';
//     else ans += '0';
//     if (s[s.size() - 1] == ans)cout << "Right";
//     else {
//         s[s.size() - 1] = ans;
//         cout << s;
//     }
//     return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// struct date
//{
//     LL x, y, z;
//     bool operator<(const date d) const
//     {
//         if (z != d.z)
//             return z < d.z;
//         if (x != d.x)
//             return x < d.x;
//         return y < d.y;
//     }
// } arr[2000];
// LL n, h, r;
// bool vis[2000];
// bool is[1010][1010];
// bool bfs(int root)
//{
//     queue<int> q;
//     q.push(root);
//     vis[root] = true;
//     if (arr[root].z > r)return 0;
//     while (q.size())
//     {
//         int u = q.front();
//         if (arr[u].z + r >= h)
//         {
//             return 1;
//         }
//         q.pop();
//         for (int i = 1; i <= n; i++)
//         {
//             if (is[u][i] && !vis[i])
//             {
//                 if ((arr[u].x - arr[i].x) * (arr[u].x - arr[i].x) + (arr[i].y - arr[u].y) * (arr[i].y - arr[u].y) +
//                     (arr[i].z - arr[u].z) * (arr[i].z - arr[u].z) <=
//                     4 * r * r)
//                     vis[i] = true;
//                 q.push(i);
//             }
//         }
//     }
//     return 0;
// }
// int main()
//{
//     int t;
//     cin >> t;
//     while (t--)
//     {
//         memset(is, 0, sizeof(is));
//         memset(vis, 0, sizeof(vis));
//         cin >> n >> h >> r;
//         for (int i = 1; i <= n; i++)
//         {
//             cin >> arr[i].x >> arr[i].y >> arr[i].z;
//         }
//
//         sort(arr + 1, arr + 1 + n);
//         for (int i = 1; i <= n; i++)
//         {
//             for (int j = i + 1; j <= n; j++)
//             {
//                 if ((arr[i].x - arr[j].x) * (arr[i].x - arr[j].x) + (arr[i].y - arr[j].y) * (arr[i].y - arr[i].y) +
//                     (arr[i].z - arr[j].z) * (arr[i].z - arr[j].z) <=
//                     4 * r * r)
//                     is[i][j] = 1;
//             }
//         }
//         int flag = 0;
//         for (int i = 1; i <= n; i++)if (vis[i] == 0)
//             if (bfs(i)) {
//                 cout << "Yes" << endl;
//                 flag = 1;
//                 break;
//             }
//         if (flag == 0)cout << "No" << endl;
//     }
// }
//  #include<bits/stdc++.h>
//  using namespace std;
//  typedef long long  LL;
//  const int N = 2e5 + 10;
//  LL arr[N];
//  struct date {
//      int l, r;
//  }brr[N];

// int main() {

//     LL t;
//     cin >> t;
//     while (t--) {
//         vector<int>v;
//         int n;
//         cin >> n;
//         for (int i = 1; i <= n; i++)cin >> arr[i];
//         for (int i = 1; i <= n; i++)cin >> brr[i].l >> brr[i].r;
//         int h = 0;
//         int flag = 0;
//         v.push_back(n);
//         for (int i = n - 1; i; i--)
//             if (brr[i].r <= brr[v[v.size() - 1]].r)v.push_back(i);
//         reverse(v.begin(), v.end());
//         int pos = 0;
//         for (int i = 1; i <= n; i++) {
//             if (arr[i] == 0) {
//                 if (h > brr[i].r || h < brr[i].l)flag = 1;
//             }
//             else if (arr[i] == 1) {
//                 h++;
//                 if (h > brr[i].r || h < brr[i].l)flag = 1;
//             }
//             else {
//                 while (pos<v.size()&&i > v[pos])pos++;
//                 if (pos == v.size())pos--;
//                 int r = brr[v[pos]].r;
//                 if (brr[i].l > r)flag = 1;
//                 else {
//                 if (h < r)arr[i] = 1;
//                 else if (h == r)arr[i] = 0;
//                 else flag = 1;
//                 }

//                 h += arr[i];
//                 if (h > brr[i].r || h < brr[i].l)flag = 1;
//             }
//         }
//         if (flag)cout << "-1" << endl;
//         else {
//             for (int i = 1; i <= n; i++)cout << arr[i] << " ";
//             cout << endl;
//         }
//     }
// // }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL arr[1010][1010];
// LL brr[1010][1010];
// int main(){
//     int n,m,k;
//     cin>>n>>m>>k;
//     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>arr[i][j];
//     for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
//         brr[i][j]=brr[i-1][j]+brr[i][j-1]-brr[i-1][j-1]+arr[i][j];
//     }
//     LL Max=-1e18;
//     int ans1=0,ans2=0;
//     for(int i=1;i+k-1<=n;i++)for(int j=1;j+k-1<=n;j++)
//         {
//             int x=i+k-1,y=j+k-1;
//             int k=brr[x][y]+brr[i-1][j-1]-brr[i-1][y]-brr[x][j-1];
//             if(Max<k)
//             {
//                 Max=k;
//                 ans1=i;
//                 ans2=j;
//             }
//         }
//     cout<<ans1<<' '<<ans2;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL ans;
//    LL arr[10]={0};
// unordered_map<LL,LL>pos;
// unordered_map<int,int>mp;
// void dfs(int n,LL sum){
//    if(n==7){mp[sum]++;return;}
//    for(int i=0;i<=arr[n];i++)
//        dfs(n+1,sum+i*pos[n]);
//}
// bool is(int n){
//    int k=6;
//    int brr[10]={0};
//    for(int i=1;i<=6;i++)cout<<arr[i]<<' ';
//    cout<<endl;
//    for(int i=1;i<=6;i++)cout<<brr[i]<<' ';
//    cout<<endl;
//
//    memcpy(brr,arr,sizeof brr);
//    while(k){
//        cout<<n<<' '<<pos[k]<<' '<<brr[k]<<endl;
//        if(n<pos[k]||brr[k]==0){k--;cout<<"$"<<endl;}
//        else {n-=pos[k];brr[k]--;cout<<"^"<<endl;}
//        cout<<n<<" "<<k<<endl;
//    }
//    if(n==0)return true;
//    return false;
//}
// int main(){
//     pos[1]=1;
//    pos[2]=2;
//    pos[3]=3;
//    pos[4]=5;
//    pos[5]=10;
//    pos[6]=20;
//    int sum=0;
//    while(1){
//   for(int i=1;i<=6;i++){
//        cin>>arr[i];
//        sum+=arr[i]*pos[i];}
//    int num=0;
//    cout<<"sum="<<sum<<endl;
//    for(int i=sum;i<=sum;i++)
//        if(is(i))num++;
//    cout<<"Total="<<num;
//    }
//
//}
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL ans;
// LL arr[10] = { 0 };
// unordered_map<LL, LL>pos;
// unordered_map<int, int>mp;
// void dfs(int n, LL sum) {
//    if (n == 7) { mp[sum]++; return; }
//    for (int i = 0; i <= arr[n]; i++)
//        dfs(n + 1, sum + i * pos[n]);
//}
// bool is(int n) {
//    int k = 6;
//    int brr[10] = { 0 };
//
//    for (int i = 1; i <= 6; i++)brr[i] = arr[i];
//    while (k) {
//        if (n < pos[k] || brr[k] == 0) { k--;  }
//        else { n -= pos[k]; brr[k]--;  }
//    }
//    if (n == 0)return true;
//    return false;
//}
// int main() {
//    pos[1] = 1;
//    pos[2] = 2;
//    pos[3] = 3;
//    pos[4] = 5;
//    pos[5] = 10;
//    pos[6] = 20;
//    int sum = 0;
//        for (int i = 1; i <= 6; i++) {
//            cin >> arr[i];
//            sum += arr[i] * pos[i];
//        }
//        cout << sum;
//        int num = 0;
//        for (int i = sum; i <= sum; i++)
//            if (is(i))num++;
//        cout << "Total=" << num;
//
//
//}
// #include<bits/stdc++.h>
// using namespace std;
// int arr[500010];
// int n, a, b;

// bool is(int time) {
//     int i = n;
//     while (i && arr[i] <= time)i--;
//     int sum = 0;
//     while (i) {
//        sum += (arr[i]-time +b-1)/ b;
//        cout << i<<' '<<time<<' '<<b<< endl;
//        i--;
//     }
//     if (time == 5 || time == 6)cout << time<<' '<<sum<<endl;
//     return sum <= time;
// }
// int main() {
//     cin >> n >> a >> b;
//     for (int i = 1; i <= n; i++)cin >> arr[i];
//     sort(arr + 1, arr + 1 + n, greater<int>());
//     int l = 1;
//     int r = arr[1];
//     while(l<r)
//     {
//         int mid = l + r >> 1;
//         if (is(mid))r = mid;
//         else l = mid + 1;
//     }
//     cout << l;
//     for (int i = 1; i <= n; i++)cout << arr[i] << ' ';
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// unordered_map<int,int>mp;
// int cou(int n){
//     int sum=0;
//     if (n == 0)return mp[0];
//     while(n){
//         sum+=mp[n%10];
//         n/=10;
//     }
//     return sum;
// }
// int main(){
//     int n;
//     cin>>n;
//     mp[0]=6;
//     mp[1]=2;
//     mp[2]=5;
//     mp[3]=5;
//     mp[4]=4;
//     mp[5]=5;
//     mp[6]=6;
//     mp[7]=3;
//     mp[8]=7;
//     mp[9]=6;
// int num=0;
//     n-=4;
//     for(int i=0;i<500;i++)
// for(int j=0;j<500;j++){
//     int k=i+j;
//         if(cou(i)+cou(j)+cou(k)==n){num++;}
// }
// cout<<num;
// }
// #include<bits/stdc++.h>
// using namespace std;
// #define x first
// #define y second
// struct date {
//    double x, y;
//    double sum;
//    bool operator<(const date d)const {
//        return sum > d.sum;
//    }
//}arr[100010];
//
// int main() {
//    int n;
//    double x1, y1, x2, y2;
//    cin >> x1 >> y1 >> x2 >> y2;
//    cin >> n;
//    for (int i = 1; i <= n; i++) {
//        double x, y;
//        cin >> x >> y;
//        arr[i].x = x;
//        arr[i].y = y;
//        arr[i].sum = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
//    }
//    arr[n + 1].sum = 0;
//    sort(arr + 1, arr + 1 + n);
//    double ans = arr[1].sum;
//    double r2 = 0;
//    for (int i = 1; i <= n; i++) {
//        double k = (arr[i].x - x2) * (arr[i].x - x2) + (arr[i].y - y2) * (arr[i].y - y2);
//        r2 = max(r2, k);
//        ans = min(ans, r2 + arr[i + 1].sum);
//    }
//    cout << ans;
//}
// #include<bits/stdc++.h>
// using namespace std;
// int main() {
// /*   string s;
//    cin >> s;
//    for (auto& i : s) {
//        if (i <= 'Z')i += 32;
//    }
//    string ss;
//    int num = 0;
//    int pos = 0;
//    int ans = 0;
//    getchar();
//    getline(cin, ss);
//    for (auto& i : ss)
//        if (i>='A'&&i <= 'Z')i += 32;
//    s = ' ' + s + ' ';
//    ss = ' ' + ss + ' ';
//    int k = 0;
//    while ((pos = ss.find(s, pos) )!= string::npos) {
//        num++;
//        if (num == 1)ans = pos;
//        pos++;
//    }
//    if (num)cout << num << ' ' << k;
//    else cout << -1;*/
//    cout << (-1 % 7);
// //}
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main() {
//     LL n;
//     cin >> n;
//     n *= 2;
//     for (LL i = 1; i<= n; i++) {
//         if (n % i == 0) {
//             LL a = i, b = n / i;
//             if ((a + b - 1) % 2 == 0 && a + b - 1 > 0) {
//                 if ((a - b + 1) % 2 == 0 && a - b + 1 > 0)
//                 {
//                     cout << (a - b + 1) / 2 << ' ' << (a + b - 1) / 2 << endl;
//                 }
//             }
//         }
//     }
// }
// #include <bits/stdc++.h>
// using namespace std;
// vector<string> v;
// int arr[30];
// size_t Max;
// int n;
//
// void dfs(int num, string s)
//{
//
//    //cout<<s<<endl;
//    Max=max(Max,s.size());
//    if (Max == 26)cout << s << endl;
//    if(num==n*2)return;
//    for(int i=0;i<n;i++){
//
//        if(arr[i]<2){
//            int length=0;
//            for (int len = 1; len <= v[i].size(); len++) {
//                string c = v[i].substr(0, len);
//                size_t pos = s.rfind(c);
//                if (pos != string::npos&&pos+c.size()==s.size()) {
//                    length = len;
//            }
//        }
//            if(length>0&&length<v[i].size()) {
//            string c=v[i].substr(0, length);
//            int pos=s.rfind(c);
//                string cp=s.substr(0,pos)+v[i];
//                arr[i]++;
//                dfs(num+1,cp);
//                arr[i]--;
//            }
//        }
//    }
//}
// int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        string s;
//        cin >> s;
//        v.push_back(s);
//    }
//    char x;
//    cin >> x;
//    for (int i = 0; i < n; i++)
//    {
//
//        string s = v[i];
//        if (s[0] != x)continue;
//        arr[i] = 1;
//        dfs(1, s);
//        arr[i]=0;
//    }
//    cout << Max;
//}

// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
//
// struct date {
//     int a, b;
// }arr[200010];
// int ans[200010];
// void solve() {
//     int n, m;
//     cin >> n >> m;
//     for (int i = 1; i <= m; i++) {
//         int x, y;
//         cin >> x >> y;
//         x--;
//         while (x >= 0) {
//
//             int a=(x + y) / n;
//             int b = (x + y) % n;
//             ans[0] += a;
//             ans[n] -= a;
//             ans[0] += b;
//
//             x--;
//         }
//     }
//     for (int i = 0; i < n; i++)cout << ans[i] << ' ';
//     cout << endl;
// }
// int main() {
//     int t;
//     cin >> t;
//     while (t--) {
//         memset(ans, 0, sizeof ans);
//         solve();
//     }
//     return 0;
// }
//  #include<bits/stdc++.h>
//  using namespace std;
//  unordered_map<int, int>mp;
//  int main() {
//      int n;
//      cin >> n;
//      mp['O'] = 7, mp['B'] = 6, mp['A'] = 5, mp['F'] = 4, mp['G'] = 3, mp['K'] = 2, mp['M'] = 1;
//      while (n--) {
//          string s1, s2;
//          cin >> s1 >> s2;
//          if (s1 == s2) {
//              cout << "same" << endl;
//          }
//          else {
//              int a = mp[s1[0]] * 10 + mp[s1[1]] - '0';
//              int b = mp[s2[0]] * 10 + mp[s2[1]] - '0';
//              if (a > b)cout << "hotter" << endl;
//              else cout << "cooler" << endl;
//          }
//      }
//  }
//  #include<bits/stdc++.h>
//  using namespace std;
//  struct date{
//  int a,b,c;
//  bool operator<(const date d)const{
//      return c>d.c;
//  }
//  }arr[100010];
//  int brr[300010];
//  int find(int x){
//      if(x==brr[x])return x;
//      return x=find(brr[x]);
//  }
//  int merge(int x,int y){
//      int X=find(x);
//      int Y=find(y);
//      brr[X]=Y;
//  }
//  int main(){
//      int N,M;
//      cin>>N>>M;
//      for(int i=1;i<=M;i++)cin>>arr[i].a>>arr[i].b>>arr[i].c;
//      sort(arr+1,arr+1+M);
//      for(int i=1;i<=2*N;i++)brr[i]=i;
//      for(int i=1;i<=N;i++){
//        auto  [a,b,c]=arr[i];
//          if(find(a)==find(b)){
//              cout<<c;
//              return 0;
//          }
//          merge(a,b+N);
//          merge(b,a+N);
//      }
//      cout<<0<<endl;
//  }
//  #include<bits/stdc++.h>
//  using  namespace std;
//  typedef long long LL;
//  LL qmi(LL a,LL b,LL mod){
//      LL ans=1;
//      while(b){
//          if(b&1)
//              ans=ans*a%mod;
//          a=a*a%mod;
//          b>>=1;
//      }return ans%mod;
//  }
//  LL gcd(LL a,LL b){
//      cout<<a<<' '<<b<<endl;
//      if(b==0)return a;
//      return gcd(b,a%b);
//  }
//  int main(){
//      LL n,m,k,x;
//      cin>>n>>m;
//      LL gc=gcd(n,m);
//      std::cout<<gc<<endl;

//     gc=n/gc*m;
//     gc/=m;
//     std::cout<<gc<<endl;
//     gc=qmi(10,k,gc);
//     gc*=m;
//     x+=gc;
//     x%=n;
//     cout<<x;
//     return 0;
// }
// #include <bits/stdc++.h>
// using namespace std;
// int num(int n)
// {
//     return (n - 1) * n / 2;
// }
// int main()
// {
//     int n, m, v;
//     cin >> n >> m >> v;
//     int vv = 1;
//     if (vv == v)
//         vv++;
//     // cout<<num(n-2)+1+n-2<<endl;
//     if (num(n - 2) + 1 + n - 2 >= m && m >= n - 1)
//     {
//         for (int i = 1; i <= n; i++)
//             if (i != v)
//             {
//                 cout << v << ' ' << i << endl;
//                 m--;
//             }
//             for (int i = 1; i <= n && m; i++)
//             {
//                 if (i == v || i == vv)
//                     continue;
//                 for (int j = i + 1; j <= n && m; j++)
//                 {
//                     if (j == v || j == vv)
//                         continue;
//                     cout << i << ' ' << j << endl;
//                     m--;
//                 }
//             }
//     }
//     else
//         cout << -1;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int brr[1010];
// int dp[10010];
// int main(){
//     int n;
//     cin>>n;;
//     int m=5000;
//     for(int i=1;i<=n;i++){
//         int a,b;
//         cin>>a>>b;
//     brr[i]=a-b;
//     }
//         memset(dp,0x3f,sizeof dp);
//         dp[0+m]=0;
//         for(int i=1;i<=n;i++)
//             for(int j=5000;j>=-5000;j--){
//                 if(j>=brr[i]>=-5000)dp[j]=min(dp[j],dp[j-brr[i]+m]+1);
//                 if(j+brr[i]<=5000)
//                 dp[j]=min(dp[j],dp[m+j+brr[i]]+1);
//             }
// int ans=0x3f3f3f3f;
//     for(int i=0;i<=5000;i++){
//         ans=min(dp[m-i],ans);
//         ans=min(dp[m+i],ans);
//         if(ans!=0x3f3f3f3f)break;
//     }
// cout<<ans;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int arr[30];
// int n;
// int q;
// int brr[20][30];
// vector<int>ans(100);
// int target[30];
// bool is(){
//     for(int i=1;i<=n;i++)
//         if(target[i]<arr[i])return false;
//     return true;
// }
// void dfs(int pos,vector<int>v){
//     if(pos==q+1){
//         if(is()){
//             // for(auto i:v)cout<<i<<' ';
//             // cout<<endl;
//             if(v.size()<ans.size())ans=v;
//         }
//         return ;
//     }
// v.push_back(pos);
//     for(int i=1;i<=n;i++)
//         target[i]+=brr[pos][i];
// dfs(pos+1,v);
//     v.pop_back();
//         for(int i=1;i<=n;i++)
//         target[i]-=brr[pos][i];
//     dfs(pos+1,v);
// }
// int main(){
//     cin>>n;
//     for(int i=1;i<=n;i++)cin>>arr[i];
//     cin>>q;
//     for(int i=1;i<=q;i++)
//         for(int j=1;j<=n;j++)cin>>brr[i][j];
//     vector<int>v;
//     dfs(1,v);
//     cout<<ans.size()<<' ';
//     for(auto i:ans)cout<<i<<' ';
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int dp[100][100][200];//从11到i1，i1+k；i2，i2+k；
// int arr[100][100];
// int main(){
//     int n,m;
//     cin>>n>>m;
//     memset(dp,-0x3f,sizeof dp);
//     dp[0][0][0]=0;
//     for(int i=1;i<=n;i++)
//     for(int j=1;j<=m;j++)cin>>arr[i][j];
//     for(int k=2;k<=n+m;k++)
//     for(int i1=1;i1<=min(k,n);i1++)
//     for(int i2=1;i2<=min(k,n);i2++){
//        int j1=k-i1;
//         int j2=k-i2;
//         if(j1>m||j2>m)continue;
//         dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1-1][i2-1][k-1]);
//             dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1-1][i2][k-1]);
//             dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1][i2-1][k-1]);
//             dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1][i2][k-1]);
//             dp[i1][i2][k]+=arr[i1][j1]+arr[i2][j2];
//         if(i1==i2&&j1==j2){
//             if(i1==1&&j1==1);
//             else if(i1==n&&j1==m);
//             else dp[i1][i2][k]=-0x3f3f3f3f;
//         }
//     }
//     cout<<dp[n][m][n+m];
//     return 0;
// }
//#include<bits/stdc++.h>
//using namespace std;
//int dp[100][100][200];//从11到i1，i1+k；i2，i2+k；
//int arr[100][100];
//int main(){
//    int n,m;
//    cin>>n>>m;
//    for(int i=1;i<=n;i++)
//    for(int j=1;j<=m;j++)cin>>arr[i][j];
//    for(int k=2;k<=n+m;k++)
//    for(int i1=max(1,k-m);i1<=k&&i1<=n;i1++)
//    for(int i2=max(1,k-m);i2<=k&&i2<=n;i2++){
//        if(i1!=i2||k==2||k==n+m){
//            dp[i1][i2][k]=max(dp[i1-1][i2-1][k-1],dp[i1-1][i2][k-1]);
//            dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1][i2-1][k-1]);
//            dp[i1][i2][k]=max(dp[i1][i2][k],dp[i1][i2][k-1]);
//            dp[i1][i2][k]+=arr[i1][k-i1]+arr[i2][k-i2];
//        }
//    }
//    cout<<dp[n][m][n+m];
//    return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//typedef long long LL;
//LL arr[1010][1010];
//LL dp[1010][1010][2];
//int main() {
//    memset(dp, -0x3f, sizeof dp);
//    int n, m;
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++) {
//            cin >> arr[i][j];
//        }
//    //0是从上到下，1是从下到上，我们规定从左到右也属于0
//    dp[0][1][1] = dp[0][1][0] = 0;
//    for (int j = 1; j <= m; j++)
//    {
//        for (int i = 1; i <= n; i++)
//            dp[i][j][0] = max({ dp[i][j - 1][0],dp[i][j - 1][1],dp[i - 1][j][0] }) + arr[i][j];
//        for (int i = n; i; i--)
//            dp[i][j][1] = max({ dp[i][j - 1][0],dp[i][j - 1][1],dp[i + 1][j][1] }) + arr[i][j];
//    }
//    cout << dp[n][m][0];
//    return 0;
//}
// #include<iostream>
// #include<algorithm>
// using namespace std;
// typedef long long LL;
// int arr[100010];
// LL N, M, C;

// bool check(int mid) {
//     int ans = 1;
//     int l = 1;
//     // cout<<mid<<endl;
//     for (int i = 1; i <= N; i++)
//     {
//         if (i - l + 1 > C) {
//             l = i; ans++;
//             if (mid == 0)
//                 cout << ans << endl;
//         }
//         else if (arr[i] - arr[l] > mid)l = i;
//         // cout<<i<<' '<<l<<' '<<arr[i]-arr[l]<<' '<<mid<<endl;
//     }
//     // if(mid==0)cout<<ans;
//     return ans <= M;
// }
// int main() {
//     cin >> N >> M >> C;
//     for (int i = 1; i <= N; i++) {
//         cin >> arr[i];
//     }
//     sort(arr + 1, arr + 1 + N);
//     int l = 0, r = arr[N];
//     while (l < r) {
//         int mid = l + r >> 1;
//         if (check(mid))r = mid;
//         else l = mid + 1;
//     }
//     cout << l;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// int main(){
//     string s;
//     cin>>s;
//     LL n;
//     cin>>n;
//     LL len=s.size();
//     while(len<n)
//     {
//         LL k=len;
//         while(k<n)k<<=1;
//         k>>=1;
//         if(k==n-1)
//             n--;
//         else n=n-k-1;
//     }
//         cout<<s[n-1];
//     return 0;
// }
// #include<iostream>
// using namespace std;
// typedef
//  long long LL;
// void solve(){
//         LL n;
//     cin>>n;
//     if(n==1)cout<<1<<endl;
//     else
//     cout<<n*(n-1)<<endl;
// }
// int main(){
//     LL t;
//     cin>>t;
//     while(t--){
//         solve();
//     }

    
//     return 0;
// }
// #include<iostream>
// #include<queue>
// #include<map>
// using namespace std;
// typedef long long LL;
// map<LL,bool>mp;

// void solve(){
//     mp.clear();
//     LL n,s;
//     cin>>n>>s;
//     queue<LL>q;
//     q.push(1);
//     mp[1]=true;
//     LL num=0;
//     while(q.size()){
//         int qsize=q.size();
//         while(qsize--){
//              auto a=q.front();
//              q.pop();
//         LL a1=a+1;
       
//         if(a==s){cout<<num<<endl;
//             return;}
//             else {
//                 LL a1=a+1;
//                  LL a2=a-1;
//                  LL a3=n/a;
//                  if(a>s){
//                     if(mp.count(a2)||a2<1);
//                 else{
//         q.push(a2);
//                 mp[a2]=true;}
//                  }
//                  else{
//                     if(mp.count(a1)||a1<1);
//                 else{
//         q.push(a1);
//                 mp[a1]=true;}
//                 if(mp.count(a3));
//                 else{
//                     q.push(a3);
//                     mp[a3]=true;
//                 }
//                  }
//             }
//         }
//        num++;
//     }
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// }
// #include<iostream>
// #include<queue>
// #include<map>
// #include<algorithm>
// #include<cmath>
// using namespace std;
// typedef long long LL;
// map<LL,bool>mp;

// void solve(){
//     mp.clear();
//     LL n,s1;
//     cin>>n>>s1;
//     LL k=sqrt(n);
//     if(k>=s1){
//         cout<<s1-1<<endl;
//     }
//     else{
//         LL s2=n/s1;
//         LL ans=1;
//         ans+=(s2-1);
//         ans+=abs(n/s2-s1);
//         cout<<ans<<endl;
//     }
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// // }
// #include<iostream>
// #include<queue>
// #include<map>
// #include<algorithm>
// #include<cmath>
// using namespace std;
// typedef long long LL;

// void solve(){
//     LL n,s1;
//     cin>>n>>s1;
//     LL k=sqrt(n);
//     LL ans1=s1-1;
//         LL s2=n/s1;
//         LL ans=1;
// //      cout<<s2<<' ';
//         ans+=(s2-1);
//         ans+=abs(n/s2-s1);
//     ans1=min(ans,ans1);
//     s2++;
//     ans=s2;
//     ans+=abs(n/s2-s1);
//     ans1=min(ans1,ans);    
//     cout<<ans1<<endl;
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int arr[200];
// struct date{
//     int pos,a;
//     bool operator<(const date d)const{
//         return a<d.a;
//     }
// }brr[200];
// void solve(){
//     int n;
//     cin>>n;
//     for(int i=1;i<=n;i++){
//         cin>>arr[i];
//         brr[i].a=arr[i];
//         brr[i].pos=i;}
//     sort(arr+1,arr+1+n);
//     sort(brr+1,brr+1+n);
//     if(arr[n]>n){cout<<-1<<endl;return ;}
//     int flag=0;
//     int num=0;
//     vector<int>v;
//     for(int i=n;i>1;i--){
//         if(arr[i]-arr[i-1]>2){
//             cout<<-1<<endl;
//             return;
//         }
//         else if(arr[i]-arr[i-1]==2){
//             flag++;
//             if(flag>1){
//                 cout<<-1<<endl;
//                 return;
//             }
//         }
//         else if(arr[i]==arr[i-1]&&arr[i]){
//             cout<<-1<<endl;
//             return;
//         }
//     }
//     int pos=0;
//     for(int i=1;i<=n;i++){
//         if(brr[i].a){
//             v.push_back(brr[i].pos);
//             num++;}
//         if(brr[i].a==1)pos=1;
//     }
//     if(pos);
//     else{
//          for(int i=n;i;i--){
//         if(brr[i].a){v.push_back(brr[i].pos);num++;}
//     }
//     }
//     cout<<v.size()<<endl;
//     for(auto i:v)cout<<i<<' ';
//     cout<<endl;
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int arr[200];
// struct date{
//     int pos,a;
//     bool operator<(const date d)const{
//         return a<d.a;
//     }
// }brr[200];
// void solve(){
//     int n;
//     cin>>n;
//     for(int i=1;i<=n;i++){
//         cin>>arr[i];
//         brr[i].a=arr[i];
//         brr[i].pos=i;}
//     sort(arr+1,arr+1+n);
//     sort(brr+1,brr+1+n);
//     if(arr[n]>n){cout<<-1<<endl;return ;}
//     int flag=0;
//     int num=0;
//     vector<int>v;
//     for(int i=n;i>1;i--){
//         if(arr[i]-arr[i-1]>2){
//             cout<<-1<<endl;
//             return;
//         }
//         else if(arr[i]-arr[i-1]==2){
//             flag++;
//             if(flag>1){
//                 cout<<-1<<endl;
//                 return;
//             }
//         }
//         else if(arr[i]==arr[i-1]&&arr[i]){
//             cout<<-1<<endl;
//             return;
//         }
//     }
//     int pos=0;
//     for(int i=1;i<=n;i++){
//         if(brr[i].a){
//             v.push_back(brr[i].pos);
//             num++;}
//         if(i>1)
//         if(brr[i].a-brr[i-1].a==2)pos=i;
//     }
//     if(pos){
//         v.clear();
//         for(int i=1;i<pos;i++)
//         if(brr[i].a)v.push_back(brr[i].pos);
//         v.push_back(brr[n].pos);
//          for(int i=pos;i<=n;i++){
//         if(brr[i].a){v.push_back(brr[i].pos);}
//     }
//     }
//     if(v.size()>n)cout<<-1<<endl;
//     else{
//             cout<<v.size()<<endl;
//     for(auto i:v)cout<<i<<' ';
//     cout<<endl;
//     }
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// int arr[100010];
// int brr[100010];
// map<int,int>mp;
// map<int,int>cou;
// int main(){
//     int n;
//     cin>>n;
//     for(int i=0;i<n;i++)cin>>arr[i];
//     for(int i=0;i<n;i++)brr[i]=arr[i];
    
//     sort(brr,brr+n);
//     int Max=brr[n-1];
//  for(int i=0;i<n;i++){
//      cou[brr[i]]++;
//  }   
//     for(int i=0;i<n;i++){
//         for(int j=1;j*brr[i]<=Max;j++){
//             if(cou[j*brr[i]]){
//                 mp[j*brr[i]]++;
//             }
//         }
//     }
//     for(int i=0;i<n;i++){
//         cout<<mp[arr[i]]-1<<endl;
//     }
// }
// #include<iostream>
// using namespace std;
// int arr[100010];
// int cnt[1000010];
// int ans[1000010];
// int main(){
//     int n;
//     cin>>n;
//     for(int i=1;i<=n;i++)cin>>arr[i];
//     for(int i=1;i<=n;i++)cnt[arr[i]]++;
//     for(int i=1;i<=100000;i++){//枚举除数
//         for(int j=i;j<=1000000;j+=i){//枚举被除数
//             {
//                 ans[j]+=cnt[i];
//             }
//         }
//     }
//     for(int i=1;i<=n;i++)cout<<ans[arr[i]]-1<<endl;
//     return 0;
// }
//#include<iostream>
//#include<queue>
//#include<cstring>
//using namespace std;
//const int N=2010;
//typedef long long LL;
//LL e[N],ne[N],w[N],su[N],h[N];
//int idx;
//void add(int a,int b,LL c,LL d){
//    e[idx]=b,ne[idx]=h[a],h[a]=idx,su[idx]=d,w[idx++]=c;
//}
//LL dp1[2000];//总费用
//LL dp2[2000];//速度
//int main(){
//    int n,m;
//    cin>>n>>m;
//    memset(h,-1,sizeof h);
//    for(int i=1;i<=m;i++){
//        int a,b,c,d;
//        cin>>a>>b>>c>>d;
//        add(a,b,c,d*1000000);
//        add(b,a,c,d*1000000);
//    }
//    memset(dp1,0x3f,sizeof dp1);
//    memset(dp2,1,sizeof dp2);
//    queue<int>q;
//    q.push(1);
//    dp1[1]=1;
//    dp2[1]=0x3f3f3f3f;
//    while(q.size()){
//        int k=q.front();
//        //std::cout<<k<<' '<<dp1[k]<<' '<<dp2[k]<<endl;
//        q.pop();
//        for(int i=h[k];i!=-1;i=ne[i]){
//            int j=e[i];
//           // cout<<j<<' ';
//            if(min(dp2[k],su[i])/(dp1[k]+w[i])>dp2[j]/dp1[j]){
//                q.push(j);
//                dp1[j]=dp1[k]+w[i];
//                dp2[j]=min(dp2[k],su[i]);
//            }
//        
//        }
//    }
//    cout<<dp2[n]/(dp1[n]-1);
//    return 0;
//}
// #include<iostream>
// #include<queue>
// #include<cstring>
// using namespace std;
// typedef long long LL;
// int dp[2100][2100];
// LL arr[2000];
// void init(){
// for(int i=0;i<=2000;i++){
//     dp[i][0]=1;
//     for(int j=1;j<=2000;j++)
//     dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
// }
// }
// int MOD=1e9+7;
// int main(){
//  LL n,m;
//     cin>>n>>m;
//     for(int i=1;i<=m;i++)cin>>arr[i];
//     init();
//     LL ans=0;
//     for(int i=0;i<n;i++){
//         int ret=dp[n][i];
//         for(int j=1;j<=m;j++){
//             ret=ret*dp[arr[j]+n-1-i][n-i-1]%MOD;
//         }
//         if(i&1)ans=((ans-ret)%MOD+MOD)%MOD;
//         else ans=(ans+ret)%MOD;
//     }
//     cout<<ans;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// LL arr[100000];
// typedef long long LL;
// LL gcd(LL a,LL b){
//     return b?gcd(b,a%b):a;
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         int n;
//         cin>>n;
//         for(int i=1;i<=n;i++)cin>>arr[i];
//         swap(arr[1],arr[2]);
//         for(int i=2;i<=n;i++){
//             arr[1]/=gcd(arr[1],arr[i]);
//             if(arr[1]==1)break;
//         }
//         if(arr[1]==1)cout<<"Yes"<<endl;
//         else cout<<"No"<<endl;
//     }
//     return 0;
// }
// #include<iostream>
// #include<queue>
// #include<cstring>
// #include<vector>
// #include<map>
// #include<algorithm>
// #include<cmath>

// using namespace std;
// typedef long long LL;
// const int N=2e5+10;
// LL arr[N];
// int main(){
//     int t;
//     cin>>t;
//     for(int i=0;i<t;i++){

//     }
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;

// vector<LL>cheng(vector<LL>&A,LL b){
//     vector<LL>C;
//     LL t=0;
//     for(int i=0;i<A.size();i++){
//         t+=A[i]*b;
//         C.push_back(t%10);
//         t/=10;
//     }
//     while(t){
//         C.push_back(t%10);
//         t/=10;
//     }
//     return C;
// }
// vector<LL> jia(vector<LL>A,vector<LL>B){
//     vector<LL>C;
//     if(A.size()<B.size())swap(A,B);
//     LL t=0;
//     for(int i=0;i<A.size();i++){
//         t+=A[i];
//         if(i<B.size())t+=B[i];
//         C.push_back(t%10);
//         t/=10;
//     }
//     while(t){
//         C.push_back(t);
//         t/=10;
//     }
//     return C;
// }
// int arr[100];
// int main(){
//     LL n,m;
//     cin>>n>>m;
//     vector<LL>ans(1,0);
//     for(int i=1;i<=n;i++){
//         for(int i=1;i<=m;i++)cin>>arr[i];
//         int l=1,r=m;
//         vector<LL>A(1,1);
//         while(l<=r){
//             A=cheng(A,2);
//             if(arr[l]<arr[r]){
//                 vector<LL>B=cheng(A,arr[l++]);
//             ans=jia(ans,B);
//             }
//             else{
//              vector<LL>B=cheng(A,arr[r--]);
//                 ans=jia(ans,B);
//             }
            
//         }
//     for(int i=ans.size()-1;i>=0;i--)cout<<ans[i];
//         cout<<endl;
//     }
    
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;
// LL dp[1010][1010][12];
// int arr[1010];
// int brr[1010];
// LL MOD=1e9+7;
// int n,m,k;
// int main(){
//     cin>>n>>m>>k;
//     for(int i=1;i<=n;i++)cin>>arr[i];
//     for(int i=1;i<=m;i++)cin>>brr[i];
//     sort(arr+1,arr+1+n);
//     sort(brr+1,brr+1+m);
//     for(int i=0;i<=n;i++)
//         for(int j=0;j<=m;j++)
//     dp[i][j][0]=1;
     
//     for(int i=1;i<=n;i++)
//         for(int j=1;j<=m;j++)
//        for(int l=1;l<=k;l++)
//             {
//                 dp[i][j][l]+=dp[i-1][j][l];
//                 dp[i][j][l]%=MOD;
//                 // std::cout<<dp[i][j][l]<<' ';
//                 dp[i][j][l]+=dp[i][j-1][l];
//                 dp[i][j][l]%=MOD;
//                 // std::cout<<dp[i][j][l]<<' ';
//                 dp[i][j][l]-=dp[i-1][j-1][l];
//                 dp[i][j][l]=(dp[i][j][l]%MOD+MOD)%MOD;
//                 // std::cout<<dp[i][j][l]<<' ';
//                 if(arr[i]>brr[j])
//                 {dp[i][j][l]+=dp[i-1][j-1][l-1];
//                 // std::cout<<dp[i][j][l]<<' ';
//             }
//                 dp[i][j][l]%=MOD;
//                 // if(dp[i][j][l]>0)cout<<i<<' '<<j<<' '<<l<<endl;
//             }
//             cout<<dp[n][m][k];
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef int LL;
// LL MOD;
// LL read(){
//     char c=getchar();
//     LL ret=0;
//     while(c<'0'||c>'9')c=getchar();
//     while(c>='0'&&c<='9'){
//         ret=ret*10+c-'0';
//         c=getchar();
//     }
//     return ret;
// }
// void print(LL x){
//     if(x>9)print(x/10);
//     putchar(x%10+'0');
// }
// LL qmi(LL a,LL b){
//     LL c=1;
//     while(b){
//         if(b&1)c=a*c%MOD;
//         a=a*a%MOD;
//         b>>=1;
//     }
//     return c;
// }
// LL kk(LL a,LL b){
// }
// LL gcd(LL a,LL b,LL&c,LL&d){
//     if(b==0){
//         c=1,d=0;
//         return a;
//     }
//     LL ret=gcd(b,a%b,c,d);
//     LL e=d;
//     d=(c-d*(a/b));
//     c=e;
//     return ret;
// }

// int main(){
//     LL n,m,l;
//     n=read();
//     m=read();
//     l=read();
//      MOD=n+1;
// LL x=qmi(2,m);
//     LL a=0,b=0;
//     gcd(x,MOD,a,b);
//     a=(a%MOD+MOD)%MOD;
//    // print(a);cout<<endl;
//     a=a*l%MOD;
//     print(a);
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// map<int,int>mp1;
// map<int,int>mp2;
// int main(){
//     int a,b;
//     cin>>a>>b;
//     for(int i=2;i*i<=a;i++)
//         {
//             if(a%i==0){
//                 int sum=0;
//                 while(a%i==0){
//                     a/=i;
//                     sum++;
//                 }
//                 mp1[i]=sum;
//             }
//         }
//     if(a>1)mp1[a]=1;
//     for(int i=2;i*i<=b;i++)
//         {
//             if(b%i==0){
//                 int sum=0;
//                 while(b%i==0){
//                     b/=i;
//                     sum++;
//                 }
//                 mp2[i]=sum;
//             }
//         }
//     if(b>1)mp2[b]=1;
//     long long ans=1;
//     for(auto i:mp2){
//         int a=i.first;
//         int b=i.second;
//         b-=mp1[a];
//         ans+=(b);
//     }
//     cout<<ans;
//     return 0;
// }
// #include<bits/stdc++.h>
// using namespace std;
// const int N=1e5+10;
// struct date{
// int a,b,c;
// bool operator<(const date d)const{
//     return c<d.a;
// }
// }arr[N];
// int fa[N];
// int Find(int x){
//     if(x==fa[x])return x;
//     return fa[x]=Find(fa[x]);
// }
// int main(){
// int n,m,k;
//     cin>>n>>m>>k;
//     k-=n;
//   for(int i=1;i<=m;i++){
//       cin>>arr[i].a>>arr[i].b>>arr[i].c;
//   } 
//     for(int i=1;i<=n;i++)fa[i]=i;
//     sort(arr+1,arr+1+m);
//     int ans=0;
//     for(int i=1;i<=m&&k;i++){
//         auto [a,b,c]=arr[i];
//         if(Find(a)==Find(b));
//         else{
//             ans+=c;
//             fa[a]=b;
//         }
//     }
//     cout<<ans;
//     return 0;
// }
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5;
int cnt[100100];
LL arr[10000010];
int main() {


    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        LL x;
        cin >> x;
        cnt[x]++;
    }
    LL sum = 0;
    int hh = 0, tt = -1;
    for (int i = 1; i <=N || hh != tt;) {
        if (cnt[i] == 0){
            if(i<=N)
            i++;
            else ;
        }
        else {
            LL x1 = i;
            LL x2 = 0x3f3f3f3f3f;
            if (hh <= tt) {
                x2 = arr[hh];
            }
            if (x1 < x2) {
                cnt[i]--;
                while (i <= N && cnt[i] == 0)i++;
            }
            else hh++;
            x1 = min(x1, x2);
            LL y1 = 0x3f3ff3f;
            if (i <=N)y1 = i;
            LL y2 = 0x3f3f3f3f;
            if (hh <= tt)
                y2 = arr[hh];
            if (y1 < y2)cnt[i]--;
            else hh++;
            y1 = min(y1, y2);
            sum += y1 + x1;
            arr[++tt] = y1 + x1;
        }
    }
    cout << sum;
    return 0;
}